#include "main.h"
#include "malloc.h"



void create_tree(BiTreeNode ** root_pp, char * pre_order_seq, int  num_elements) {
    static int num_element = -1;
    num_element++;
    if (pre_order_seq[num_element] != '\0' && pre_order_seq[num_element] != '#') {
        (*root_pp) = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        (*root_pp)->data = pre_order_seq[num_element];
        create_tree(&((*root_pp)->leftChild), pre_order_seq, num_elements);
        create_tree(&((*root_pp)->rightChild), pre_order_seq, num_elements);
    }
    else {
        (*root_pp) = 0;
    }
}

void pre_order_traverse(BiTreeNode *t, void visit(DataType item))
{
    if (t!=NULL){
        visit(t->data);
        pre_order_traverse(t->leftChild,visit);
        pre_order_traverse(t->rightChild,visit);
    }
}

//使用visit(item)函数中序遍历二叉树t
void in_order_traverse(BiTreeNode *t, void visit(DataType item))
{
    if (t!=NULL){
        in_order_traverse(t->leftChild,visit);
        visit(t->data);
        in_order_traverse(t->rightChild,visit);
    }
}

//使用void visit(DateType item)函数后序遍历二叉树t
void post_order_traverse(BiTreeNode *t, void visit(DataType item))
{
    if (t!=NULL){
        post_order_traverse(t->leftChild,visit);
        post_order_traverse(t->rightChild,visit);
        visit(t->data);
    }
}

// 可以无需更改本函数的实现
void visit(DataType item)
{
    printf("%c ", item);
}

// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode * search(BiTreeNode *root, DataType x)
{
    BiTreeNode *find=NULL;
    return find;
}

// 递归地销毁由 *root 所指向根节点的树：释放该树涉及的所有动态分配的内存空间
void destroy(BiTreeNode **root)
{
    if (*root==NULL||root==NULL){
        return;
    }
    destroy(&((*root)->leftChild));
    destroy(&((*root)->rightChild));
    free(*root);
    *root=NULL;
}

void main(void)
{
    BiTreeNode *root, *p, *pp,*find;

    char * pre_order_seq = "ABC##DE#G##F###";

    create_tree(&root, pre_order_seq, 15);

    pre_order_traverse(root, visit); // 输出应该为 A B C D E G F
    printf("\n");
    in_order_traverse(root, visit); // 输出应该为 C B E G D F A
    printf("\n");
    post_order_traverse(root, visit); // 输出应该为 C G E F D B A

}